跳到主要内容

用 Go 制作一个脚本语言-2

语法分析阶段​

继续这图：

语言处理器在词法分析阶段将程序拆分成单词后，将开始构造抽象语法树（AST），而这个构建语法树属于语法分析（它依旧位于前端阶段）

BinaryExpr 作为根节点，这个 BinaryExpr 用于表示双目运算表达式，这个双目运算指的是四则运算等一些通过左值和右值计算新值的运算。

例如上图包含两个 BinaryExpr 对象，其中一个表示乘法运算 x * 2，另一个用于表示加法运算 13 加 x * 2。加法运算的左侧是整型字面量 13，右侧是另一个 BinaryExpr 对象 x * 2

而上面那个表达式若变成

(13 + x) * 2

那乘法的左值就不再是 x 而是 13 + x

设计节点​

整体使用组合模式，抽象语法树所有的节点类都是 ASTree 的子类

  • ASTLeaf 和 ASTList 是 ASTree 的直接子类
  • ASTLeaf 是叶节点（不含树枝的节点）的父类
  • ASTList 是含有树枝的节点对象的父类
  • 其它类都是 ASTLeaf 和 ASTList 的子类

如下图所示：

BNF 范式​

BNF(Backus-Naur Form) 是描述编程语言的文法，其中 BNF 中用到的元符号

元符号作用
{ pat }模式 pat 至少重复 0 次
[ pat ]与重复出现 0 次或 1 次的模式 pat 匹配
`pat1pat2`
()将括号内视为一个完整的模式

例如下所示：

factor:     NUMBER | "(" expression ")"
term:       factor { ("*" | "/") factor }
expression: term   { ("+" | "-") term   }

在 BNF 的表达规则中：: 左侧写的内容能够用于表示与在 : 右侧所写的模式相匹配的单词序列。

提示

在 BNF 中有很多变种，这个 : 有时候也写成 ::=，非终结符也可能会写成 <term> 这样，本篇使用的就是 BNF 的拓展版本 EBNF

例如：

factor:     NUMBER | "(" expression ")"

: 左侧出现的诸如 factor 这样的符号称为非终结符或元变量，说白了就是标识这类数据的名称

NUMBER 这种由大写字母组成的名称，以及由双引号 " 括起来的诸如 "(" 的符号就是终结符。这里的 NUMBER 表示任意一个整型字面量单词，"(" 表示一个内容为左括号的单词。

: 右侧的模式中也包含了若干个终结符或非终结符。这些模式里面也可以使用上表列出的那些特殊符号，如上使用 | 进行分割。

注意如果右边含有类似于 expression 这样的非终结表达符，与该部分匹配的单词序列必须与另外定义的 expression 模式匹配。如下：

factor:     NUMBER | "(" expression ")"
expression: term   { ("+" | "-") term   }

非终结符可以理解为常用模式的别称，在定义其它模式时能够引用这些非终结符。

如下的 term 项表示一种由 factor 与运算符 * 或 / 构成的序列

term:       factor { ("*" | "/") factor }
提示

这个由 { } 括起来的模式至少重复 0 次

这个表达式的意思是：与模式 term 匹配的内容，是一个与 factor 相匹配的单词序列，或是在一个与 factor 相匹配的单词序列后由运算 * 或 / 以及 factor 构成的组合再重复若干次得到的序列

所以也不难猜出，上面这个匹配的是 x * y 或者 x / y 这两种表达式，由此可以推出下面这个 expression 表达式就是一个四则运算

expression: term   { ("+" | "-") term   }

把上面三个 BNF 以图片的形式画出来：

图中的圆圈表示终结符，矩形表示非终结符

由上的表达式来分析一个具体的例子：

13 + 4 * 2

在经过词法分析后将得到如下的单词序列

NUMBER "+" NUMBER "*" NUMBER

它的匹配如下：

根据语法规则，单独的整型字面量单词能与 factor 匹配，单个 factor 又能与 term 匹配。如上可以发现 expression、term 与 factor 是范围逐层缩小的组成单位

不过值得注意当出现括号时 factor 能够回到 expression，所以 BNF 也是具有循环结构的递归定义，如下：

(13 + 4) * 2
备注

如上可以看到 BNF 可以出现无限嵌套的模式，而正则表达式里面是不允许这种情况的，所以如果要设计一种能在表达式中使用括号的程序语言，就只能通过 BNF 来定义语法了。

其实不需要使用 { } 也可以递归，如下：

expression : term | expression ("+" | "-") term

构建抽象语法树​

由上面的 BNF 结果可以构建一个语法树，如下

上面的 BNF 语法规则中已经隐含了运算符 + 与 之间的优先级，其中乘法运算符 是 term 的一部分，+ 用于将 term 相加，于是 * 的优先级自然要高于 +

所以，这里可以设计一下自创语言的 BNF 表达式

primary   : "(" expr ")" | NUMBER | IDENTIFIER | STRING
factor    : "-" primary | primary
expr      : factor { OP factor }
block     : "{" [ statement ] {(";" | EOL) [statement]} "}"
simple    : expr
statement : "if" expr block [ "else" block ] | "while" expr block | simple
program   : [ statement ] (";" | EOL)

下面分别介绍它们的意思：

  • primary 用于表示基本构成元素
  • factor 或表示一个 primary，或者表示一个前面有 - 的 primary
  • expr 用于表示表达式，表示两个 factor 之间夹有一个双目运算符的组合
  • block 指的是使用 { } 括起来的 statement（语句），而 statement 之间需要使用分号或换行符 EOL 分隔
  • statement 可以是 if 语句，while 语句或是最简单的表达式 simple
  • 最后的 program 是一个终结符，它可以包含一个完整的语句

如上设计了 statement 和 program 两种类型，其中 statement 可以省略，而 program 既可以是出于代码块外的一条语句，也可以是一行完整的程序。

写好了 BNF 语法规则后就需要编写一个解析库，不过这个 Parser 库的生成可以通过其它工具来自动生成，例如 c 语言的 yacc 等工具

提示

例如 Go 就有 goyacc 这个项目

References​